// 给定两个字符串 S、字符串 T，请在字符串 S 中找出：包含 T 中所有字符的最小连续子串。
// 其中：（1）子串字符顺序可以和 T 不同。（2）子串对应的字符频数可以大于 T 。

var minWindow: (s: string, t: string) => string = function (s, t) {
    // 边界判断
    if (s.length < t.length) {
        return "";
    }
    // 初始化哈希表，并记录t的字符频数
    const sHash = new Map<string, number>();
    const tHash = new Map<string, number>();
    for (let str of t) {
        updateHash(tHash, str);
    }
    // 初始化滑动窗口数值，范围为左闭右开
    let left: number = 0;
    let right: number = 0;
    // dis变量表示s子串与满足t的差距（算法上叫有效距离）；minLen需要动态维护，表示s的最小子串的长度
    let dis: number = 0;
    let minLen: number = s.length + 1;
    let res: string = "";
    // 滑动窗口算法
    while (right < s.length) {
        // 当前字符为t中不含的字符
        if (!tHash.has(s[right])) {
            right++;
            // 当前字符为t中包含的字符
        } else {
            // 观察新进字符有效时，有效距离+1
            if ((sHash.get(s[right]) || 0) < (tHash.get(s[right]) || 0)) {
                dis++;
            }
            updateHash(sHash, s[right]);
            right++;
            // 当有效距离满足要求时
            while (dis === t.length) {
                // 维护minLen和res
                if (right - left < minLen) {
                    minLen = right - left;
                    res = s.slice(left, right);
                }
                // 如果当前左边界字符是属于有效字符
                if (sHash.has(s[left])) {
                    // 判断是否需要更新有效距离
                    if (tHash.get(s[left]) === sHash.get(s[left])) {
                        dis--;
                    }
                    // 更新S的哈希表，左指针
                    sHash.set(s[left], sHash.get(s[left]) || 0 - 1);
                    left++;
                } else {
                    // 无效字符，直接左指针缩减
                    left++;
                }
            }
        }
    }
    return res;
};

// 哈希表更新函数
function updateHash(hashMap: Map<string, number>, elem: string) {
    if (hashMap.has(elem)) {
        hashMap.set(elem, hashMap.get(elem) || 0 + 1);
    } else {
        hashMap.set(elem, 1);
    }
}
